package MiddlePractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Demo15 {
	
//	15. 三数之和
//	给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
	
	//思路：找到i -> 去找剩下数组的j+k=0的两个数    算法复杂O(n)
	//如何避免重复：先排序，然后再找。这样主要i j k遇到同样的数，就往后跳，因为有序，所以跳到不重复为止即可
	
	public List<List<Integer>> threeSum(int[] nums) {
		
		List<List<Integer>> ans = new LinkedList<>();
		if(nums.length <= 2 || nums == null)
			return ans;
		
		Arrays.sort(nums);
		
		for(int i=0; i<nums.length-2; i++) {
			//先确定第一个数i
			if(nums[i] > 0)	break;	//不用找了，数组有序，不可能有
			if(i>0 && nums[i-1] == nums[i])	continue;	//i重复了  跳
			
			int target = -1 * nums[i];
			int j = i+1, k = nums.length-1;	//一个从左找，一个从右找
			while(j < k) {
				
				if(target == nums[j] + nums[k]) {
					ans.add(Arrays.asList(nums[i], nums[j], nums[k]));
					j++;k--;
					
					while(j < k && nums[j-1] == nums[j])	j++;
					while(j < k && nums[k] == nums[k+1])	k--;
					
				}
				else if(target > nums[j] + nums[k]) {
					j++;
				}
				else {
					k--;
				}
				
			}
		}
		
		return ans;
    }
	
}
